#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
//int main()
//{
//	printf("Hello Nowcoder!");
//	return 0;
//}
//
//#include <stdio.h>
//int main()
//{
//	printf("     **     \n");
//	printf("     **     \n");
//	printf("************\n");
//	printf("************\n");
//	printf("    *  *     \n");
//	printf("    *  *     \n");
//
//	return 0;
//}
//

//int main()
//{
//	int n = 0;
//	scanf("%d", &n);
//	printf("%d", n);
//	return 0;
//}
//
//int main()
//{
//	double n = 0;
//	scanf("%lf", &n);
//	printf("%lf", n);
//	return 0;
//}
//
//int main()
//{
//	char n = 0;
//	scanf("%c", &n);
//	printf("%c", n);
//	return 0;
//}

//int main()
//{
//	int n = 0;
//	int a = 0;
//	int b = 0;
//	int c = 0;
//	scanf("%d %d %d", &a, &b, &c);
//	printf("%d", b);
//	
//	return 0;
//}

//int main()
//{
//	char n = 0;
//	scanf("%c", &n);
//	int i = 0;
//	for (i = 0; i <= 2; i++)
//	{
//		int j = 0;
//		for (j = 0; j <= 2; j++)
//		{
//			printf("%c", n);
//		}
//		printf("\n");
//	}
//	return 0;
//}

//int main()
//{
//	char n = 0;
//	scanf("%c", &n);
//	printf("  %c  \n", n);
//	printf(" %c%c%c \n", n, n, n);
//	printf("%c%c%c%c%c\n", n,n,n,n,n);
//	printf(" %c%c%c \n", n, n, n);
//	printf("  %c  \n", n);
//
//
//	return 0;


//int main()
//{
//	char n = 0;
//	scanf("%c", &n);
//	printf("%d", n);
//	return 0;
//}

//int main()
//{
//	double n = 0;
//	scanf("%lf", &n);
//	printf("%.0lf", n);
//	return 0;
//}
//
//int main()
//{
//	int n = 0;
//	scanf("%d", &n);
//	printf("%2d", n);
//		return 0;
//}

//int main()
//{
//	int ch;
//	int ma;
//	int en;
//	scanf("%d %d %d", &ch, &ma, &en);
//	printf("score1=%d,score2=%d,score3=%d", ch, ma, en);
//	return 0;
//}
//
//int main()
//{
//    int a;
//    double b, c, d;
//    scanf("%d;%lf,%lf,%lf", &a, &b, &c, &d);
//    b = (int)(b * 100 + 0.5) / 100.0;
//    printf("The each subject score of  No. %d is %.2lf, %.2lf, %.2lf.", a, b, c, d);
//    return 0;
//}
//int main()
//{
//	int y, m, d;
//	scanf("%4d%2d%2d", &y, &m, &d);
//	printf("year=%d\n", y);
//	printf("month=%02d\n", m);
//	printf("date=%02d\n", d);
//
//	return 0;
//}

//int main()
//{
//	int a,b,c;
//	scanf("a=%d,b=%d", &a, &b);
//	c = a;
//	a = b;
//	b = c;
//	printf("a=%d,b=%d", a, b);
//
//	return 0;
//}


//int main()
//{
//	char a;
//	while (scanf("%c", &a) != EOF)
//	{
//
//		if (a >= 'A' && a <= 'Z')
//		{
//			a = a + 32;
//			printf("%c\n", a);
//		}
//	
//	}
//	return 0;
//}
//
//int main()
//{
//	int a = 0;
//	a = 0xABCDEF;
//	printf("%15d", a);
//	return 0;
//}
//
//int main()
//{
//	int a = 1234;
//	printf("%#o %#X", a, a);
//	return 0;
//}

//int main()
//{
//    char a;
//    int b;
//    float c;
//    scanf("%c\n%d\n%f", &a, &b, &c);
//    printf("%c %d %.6f", a, b, c);
//    return 0;
//}

//int main()
//{
//	int a, b, c;
//	scanf("%d %d %d", &a, &b, &c);
//	printf("%d%8d%8d", a, b, c);
//	return 0;
//}

//int main()
//{
//	int a,b;
//	scanf("%x %o", &a, &b);
//	printf("%d", a + b);
//	return 0;
//}

//int main()
//{
//	int a, b;
//	scanf("%d %d", &a, &b);
//	printf("%d", a + b);
//	return 0;
//}

//int main()
//{
//	int a, b;
//	scanf("%d %d", &a, &b);
//	printf("%d", a/b);
//	return 0;
//}

//int main()
//{
//	int a, b;
//	scanf("%d %d", &a, &b);
//	printf("%d", a%b);
//	return 0;
//}

//int main()
//{
//	float a = 0;
//	scanf("%f", &a);
//	printf("%d", (int)a % 10);
//
//	return 0;
//}

//int main()
//{
//	int fri = 0;
//	scanf("%d", &fri);
//	printf("%d\n", fri * 100);
//	return 0;
//}
//
//int main()
//{
//	int a, b;
//	scanf("%d %d", &a, &b);
//	printf("%d %d", a / b, a % b);
//	return 0;
//}

//int main()
//{
//	int a = 0;
//	scanf("%d", &a);
//	if (a >= 0)
//	{
//		printf("%d", a % 10);
//	}
//	else
//	{
//		printf("%d", (-1 * a) % 10);
//	}
//	return 0;
//}

//int main()
//{
//	int a = 0;
//	scanf("%d", &a);
//	if (a >= 0)
//	{
//		printf("%d", (a / 10)%10);
//	}
//	else
//	{
//		printf("%d", ((-1 * a) / 10)%10);
//	}
//	return 0;
//}
//
//int main()
//{
//	int d, l, c;
//	scanf("%d %d", &d, &l);
//	c = (d + l) % 7;
//	if (c == 0)
//		c = 7;
//	printf("%d\n", c);
//
//	return 0;
//}

//int main()
//{
//	int seconds, h, m, s;
//	scanf("%d", &seconds);
//	h = seconds / 3600;
//	m = (seconds % 3600) / 60;
//	s = ((seconds % 3600) % 60);
//	printf("%d %d %d", h, m, s);
//
//	return 0;
//}
//
//int main()
//{
//	int n;
//	scanf("%d", &n);
//	printf("%d", 2 << (n - 1));
//	return 0;
//}
//#include <math.h>
//int main()
//{
//	int age;
//	scanf("%d", &age);
//	long long a = age * 3.156 * (pow(10, 7));
//	printf("%lld", a);
//	return 0;
//}

//int main()
//{
//	double arr[100] = { 0 };
//	int n = 0;
//	int i = 0;
//	scanf("%d", &n);
//	for (i = 0; i < n; i++)
//	{
//		scanf("%lf", &arr[i]);
//	}
//	double max = arr[0];
//	double min = arr[0];
//	for (i = 0; i < n; i++)
//	{
//		if (arr[i] > max)
//		{
//			max = arr[i];
//		}
//	}
//	for (i = 0; i < n; i++)
//	{
//		if (arr[i] < min)
//		{
//			min = arr[i];
//		}
//	}
//	double a = 0;
//	for (i = 0; i < n; i++)
//	{
//		a += arr[i];
//	}
//	printf("%.2lf %.2lf %.2lf", max, min, a / n);
//	return 0;
//}
//#include <math.h>
//int main()
//{
//	double a, b, c;
//	scanf("%lf %lf %lf", &a, &b, &c);
//	double m, n,s;
//	m = a + b + c;
//	n = m / 2;
//	s = sqrt(n * (n - a) * (n - b) * (n - c));
//	printf("circumference=%.2lf area=%.2lf", m, s);
//
//	
//	return 0;
//}

//int main()
//{
//	int n, h, m;
//	scanf("%d %d %d", &n, &h, &m);
//	int a = m / h;
//	if(a==0)
//		printf("%d", n -a);
//	else
//		printf("%d", n-(a+1));
//
//	return 0;
//}

//int main()
//{
//	double f;
//	double c;
//	scanf("%lf", &f);
//	c = 5.0 / 9.0 * (f - 32);
//	printf("%.3lf", c);
//	return 0;
//}

//int main()
//{
//	double r;
//	scanf("%lf", &r);
//	double R;
//	R = 3.14 * r * r;
//	printf("%lf", R);
//	return 0;
//}

//int main()
//{
//	double r1, r2, R;
//	scanf("%lf %lf", &r1, &r2);
//	R = 1 / (1 / r1 + 1 / r2);
//	printf("%lf", R);
//	return 0;
//}
//int main()
//{
//	int h, r;
//	double V;
//	scanf("%d %d", &h, &r);
//	V = 3.14 * h * r * r / 1000;
//	double c = 10;
//	int d = 0;
//	while (c > 0)
//	{
//		c = c - V;
//		d++;
//	}
//	printf("%d", d);
//	return 0;
//}
//
//int main()
//{
//	int h, r;
//	double V;
//	scanf("%d %d", &h, &r);
//	V = 3.14 * h * r * r / 1000;
//	double c = 10;
//	int a = 0;
//	a = c / V;
//	if (a * V != c)
//		a++;
//	printf("%d", a);
//
//
//	return 0;
//}